package com.ry.day1129;
import java.util.*;


public class LC121 {
    static class Solution {
        /**
         * @param start: a string
         * @param end:   a string
         * @param dict:  a set of string
         * @return: a list of lists of string
         * we will sort your return value in output
         */
        public List<List<String>> findLadders(String start, String end, Set<String> dict) {
            //BFS end -> start
            //DFS start -> end
            List<List<String>> ans = new ArrayList<>();
            if(start.equals(end)){
                List<String> tmp = new ArrayList<>();
                tmp.add(start);
                tmp.add(end);
                ans.add(tmp);
                return ans;
            }
            dict.add(start);
            dict.add(end);
            Map<String,Set<String>> g = new HashMap<>(); //建立图
            Queue<String> q = new LinkedList<>();
            Set<String> vistied = new HashSet<>();
            q.add(end); //从end -> start 方向推
            boolean find = false;

            while (!q.isEmpty()){
                for (String s : q) {
                    vistied.add(s);
                }

                int size = q.size();
                Set<String> nextdata = new HashSet<>(); //存储下一层的数据
                for (int i = 0; i < size ; i++) {
                    String cur = q.poll();
                    List<String> nexts = getNext(cur.toCharArray(),dict,vistied);
                    for (String next : nexts) {
                        if(!g.containsKey(next)){
                            g.put(next,new HashSet<>());
                        }
                        g.get(next).add(cur);
                        if(next.equals(start)){
                            find = true;
                        }
                        nextdata.add(next);
                    }
                }

                if(find) break;

                for (String nd : nextdata) {
                    q.add(nd);
                }
            }

            dfs(start,end,g,new ArrayList<String>(),ans);
            return ans;
        }

        //图的深度DFS, start->end方向
        public void dfs(String cur,String end,Map<String,Set<String>> g,
                        List<String> list,List<List<String>> ans){

            list.add(cur);
            if(cur.equals(end)){//找到一条路径了
                ans.add(new ArrayList<>(list));
                list.remove(list.size()-1); //恢复现场，因为还要找其他的路径
                return;
            }


            if(g.containsKey(cur)){
                for (String next : g.get(cur)) {
                    dfs(next,end,g,list,ans);
                }
            }
            list.remove(list.size()-1); //恢复现场
        }

        public List<String> getNext(char[] arr,Set<String> dict,Set<String> visited){
            List<String> ans = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                char bak = arr[i];
                for (char c = 'a'; c <='z' ; c++) {
                    if(arr[i] == c) continue;
                    arr[i]= c;
                    String s2 = new String(arr);
                    if(dict.contains(s2) &&!visited.contains(s2)){
                        ans.add(s2);
                    }
                }
                arr[i] =bak;
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Set<String> s1 = new HashSet<>();
        s1.add("a");
        s1.add("b");
        s1.add("c");

        Solution obj = new Solution();
        System.out.println(obj.findLadders("a","c",s1));

        s1.clear();
        s1.add("hot");s1.add("dot");s1.add("dog");s1.add("lot");s1.add("log");
        System.out.println(obj.findLadders("hit","cog",s1));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
121 · 单词接龙 II
算法
困难
通过率
29%

题目
题解53
笔记
讨论99+
排名
记录
描述
给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。

变换规则如下：

每次只能改变一个字母。
变换过程中的中间单词必须在字典中出现。
最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


所有单词具有相同的长度。
所有单词都只包含小写字母。
题目确保存在合法的路径。
单词数量小于等于10000
单词长度小于等于10
样例
样例 1：

输入：

start = "a"
end = "c"
dict =["a","b","c"]
输出：

[["a","c"]]
解释：

"a"->"c"

样例 2：

输入：

start ="hit"
end = "cog"
dict =["hot","dot","dog","lot","log"]
输出：

[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：

1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"

相关知识
学习《2024年7月北美大厂最新面试真题精讲》课程中的3.9Meta：最新面试精选005相关内容 ，了解更多相关知识！
标签
相关题目

120
单词接龙
困难

790
符号串生成器
中等
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
45 分 00 秒
123456789101112


    控制台
            历史提交

 */
